package com.hqq.exercise.tree;

/**
 * AVLNodeInsert 在二叉树中插入节点
 * 题目描述:
 * 给定一棵二叉查找树和一个新的树节点，将节点插入到树中。
 * 你需要保证该树仍然是一棵二叉查找树。
 * 输入样例和输出样例:
 * 2             2
 * / \           / \
 * 1   4   -->   1   4
 * /             / \
 * 3             3   6
 * Created by heqianqian on 2017/8/30.
 */
public class AVLNodeInsert {

    /**
     * @param root: The root of the binary search tree.
     * @param node: insert this node into the binary search tree
     * @return The root of the new binary search tree.
     */
    public static TreeNode insertNode(TreeNode root, TreeNode node) {
        // write your code here
        if (root == null) {
            return node;
        }
        TreeNode head = root;
        while (root != null) {
            if (root.val > node.val) {
                if (root.left == null) {
                    root.left = node;
                    return head;
                } else {
                    root = root.left;
                }
            } else {
                if (root.right == null) {
                    root.right = node;
                    return head;
                } else {
                    root = root.right;
                }
            }
        }
        return head;
    }

}
